Regular Expression Matching

Implement regular expression matching with support for ‘.’ and ‘*’.

  1. '.' Matches any single character.
  2. '*' Matches zero or more of the preceding element.
  4. The matching should cover the entire input string (not partial).
  6. The function prototype should be:
  7. bool isMatch(const char *s, const char *p)
  9. Some examples:
  10. isMatch("aa","a") → false
  11. isMatch("aa","aa") → true
  12. isMatch("aaa","aa") → false
  13. isMatch("aa", "a*") → true
  14. isMatch("aa", ".*") → true
  15. isMatch("ab", ".*") → true
  16. isMatch("aab", "c*a*b") → true

Solution:

  1. public class Solution {
  2.   public boolean isMatch(String s, String p) {
  3.     int n = s.length(), m = p.length();
  5.     boolean[][] dp = new boolean[n + 1][m + 1];
  7.     // initialize
  8.     dp[0][0] = true;
  10.     for (int j = 1; j <= m; j++)
  11.       dp[0][j] = j > 1 && p.charAt(j - 1) == '*' && dp[0][j - 2];
  13.     for (int i = 1; i <= n; i++) {
  14.       for (int j = 1; j <= m; j++) {
  15.         if (p.charAt(j - 1) != '*')
  16.           dp[i][j] = dp[i - 1][j - 1] && isMatch(s.charAt(i - 1), p.charAt(j - 1));
  17.         else
  18.           dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && isMatch(s.charAt(i - 1), p.charAt(j - 2));
  19.       }
  20.     }
  22.     return dp[n][m];
  23.   }
  25.   boolean isMatch(char a, char b) {
  26.     return a == b || b == '.';
  27.   }
  28. }